The effective encoding and transmission of XY coordinate data between a host computer and a graphics display device has long been an issue in computer graphics. Generally, each XY coordinate is encoded into a short stream of bytes which is then transmitted to the display device. Many schemes have been developed to encode these coordinates, some with the goal of maintaining human readability, others with the goal of simple decoding by hardware logic in the receiving device.
Conventional hardware oriented implementations use groups of bits in transmitted bytes to hold partial XY coordinate data. The receiving device accumulates bits from several bytes to obtain a complete XY specification. Some of these conventional methods use one or two bits in each byte to specify which parts of the XY coordinate are represented by the other data bits. While such conventional methods can be fairly compact, They are most efficient when dealing in numbers which are powers of two because fixed numbers of bits can be dedicated to representing each of the X and Y values.
As graphic systems have increased in performance, users' expectations for that performance have increased. However, the transmission media currently available to transfer data from a host computer system to a graphics display device vary greatly in bandwidth, ranging from thousands of bits per second to tens of millions of bits per second. The most readily available and least expensive communications media are at the low end of that range. Meeting high performance expectations over a low bandwidth transmission line requires very efficient encoding of XY coordinate data.
Another consideration in sending XY coordinate data to a receiving system is that the data is often sent over a communications path which puts restrictions on the byte values that may be transmitted. For example, the characteristics of the communications path may be such that either 7 or 8 bits of each byte are accessible to the sender and receiver. Thus, the encoding scheme must be able to function in environments where the magnitude of the value transmitted in each byte may be either 2.sup.8 =256 or 2.sup.7 =128. In practice, the range of values which a byte may take is reduced even further, as some specific values may be reserved for system and other uses.
The present invention provides a method and apparatus for the efficient encoding of absolute XY data, that involves combining XY (and possibly additional) data into a single value using a mixed radix polynomial. This value is fully independent of the characteristics of the communications path, and can be broken down into a number of bytes which are compatible with the communications path. This is done using a fixed radix polynomial. The result is a smaller number of bytes being transmitted than is generally possible with existing encoding schemes, in practice as few as three bytes for a 2560.times.2560 pixel display, using only 190 of the 256 values available in an 8-bit byte.
The encoding is based on the vertical and horizontal resolution of the graphics bitmap. Resolutions need not be a power of two, and the bitmap being addressed need not have a 1:1 aspect ratio. For example, a bitmap with a resolution of 800.times.600 can be accommodated efficiently. The maximum resolution which can be encoded is unlimited in theory, and in practice is limited only by the ability of the sending and receiving devices to perform sufficiently long multiplications and divisions efficiently.
The present invention adjusts to the resolution of the XY coordinates being transmitted and lower resolution bitmaps can be addressed by transmitting fewer bytes of data than must be sent for higher resolution bitmaps.
Fewer bytes than necessary to address the entire bitmap may be sent whenever it is permissible to address only a sub-window of the bitmap. The encoding scheme requires that each encoded number includes a limited range of values between 0 and a positive maximum. However, by applying previously established offsets to the coordinates before they are encoded, and removing the offsets after they are decoded, this sub-window may be located anywhere in the larger bitmap. With use of correct offsets, any contiguous range of negative and/or positive integers may be encoded.
It is also possible to encode coordinates with resolutions higher than those of the on-screen bitmap. This is useful when addressing a larger bitmap which is displayed on a small screen acting as a viewport which may be moved around the larger bitmap by the user, without forcing the retransmission of graphic data as the viewport is moved. It also allows a low resolution device to display a portion of an image created for display on a higher resolution device.
Once the sending and receiving devices have determined the number of bytes required to encode an arbitrary XY coordinate, it is usually the case that an additional value can be encoded without increasing the number of bytes required. This can be used, for example, to allow graphics commands to be encoded into the XY data without incurring any additional transmission overhead. Multiple additional values can be encoded if so desired.
In general, the coordinate system encoded according to the present invention may be n-dimensional. The data being encoded may include coordinates for two or three dimensional graphics data, as well as other data. The encoded data need not include XY or XYZ coordinate data at all, but rather may include any finite set of values whose members have finite ranges. Examples include the encoding and decoding of XY coordinates and a color, or XYZ coordinates and a color, or XYZ coordinates and a color and one or more commands such as, for example, a command to draw a circle, the XY coordinates of its center, the length of its radius, its color, the width of the line used to draw it, and an index into a list of patterns for that line.
The transmitted data can be packaged in such a way that transmission paths which can handle 7 or 8 bit bytes can be used efficiently, and the bytes that are created can avoid certain ranges of codes, for use in transmitting non-XY data.
The encoding scheme compresses many types of data better than a simple ASCII encoding, but also better than even the "binary" information stored on mass storage devices A single instance of a variable of the enumerated type of the Pascal computer language is generally stored as a 16-bit value in a binary file. Using this encoding, only the number of states of that enumerated type is encoded, generally allowing many enumerated types to be stored in a very small number of bytes. A single byte could hold up to five of these variables having three states apiece--a binary file would generally save these in ten bytes.
The present invention is effective for use over communications paths of any bandwidth, and to and from mass storage and retrieval systems. While the examples show transmission over a byte-wise communications path, it will adapt to a path of any width, including local busses within a computer.